/**
 * 螺旋矩阵 2
 *
 * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：[[1,2,3],[8,9,4],[7,6,5]]
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：[[1]]
 *
 * 提示：
 * 1 <= n <= 20
 */

/**
 * 这题和 54. 螺旋矩阵一样, 只不过这题是赋值了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {

    // 定义全局变量
    int[][] nums;
    int n;

    // tmp 是要进行的赋的值
    int tmp = 1;

    public int[][] generateMatrix(int len) {

        // 初始化
        n = len;
        nums = new int[n][n];

        // m : 要进行的层数
        int m = (n + 1) / 2;

        for (int i = 0; i < m; i++) {

            // 循环 m 层
            dfs(i);
        }

        // 返回结果
        return nums;
    }

    /**
     * 对第 k 层进行赋值
     *
     * @param k : 第几层
     */
    private void dfs (int k) {

        // 右
        for (int i = k; i < n - k; i++) {
            nums[k][i] = tmp;
            tmp++;
        }

        // 下
        for (int i = k + 1; i < n - k - 1; i++) {
            nums[i][n - k - 1] = tmp;
            tmp++;
        }

        // 这里看下上下是否重叠了, 要是重叠了就不用在进行一次赋值了
        if (n - k - 1 == k) {
            return;
        }

        // 左
        for (int i = n - k - 1; i >= k; i--) {
            nums[n - k - 1][i] = tmp;
            tmp++;
        }

        // 上
        for (int i = n - k - 1 - 1; i > k; i--) {
            nums[i][k] = tmp;
            tmp++;
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
        test.generateMatrix(3);
    }
}